package leetcode.hot100;

@SuppressWarnings("all")
public class _75_颜色分类_双指针 {

    // 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序
    // 使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列
    // 使用整数 0、 1 和 2 分别表示红色、白色和蓝色
    // 输入：nums = [2,0,2,1,1,0]
    // 输出：[0,0,1,1,2,2]
    private int[] nums;

    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("参数异常");
        }
        this.nums = nums;
        // 如果遇到0就交换到最左边，并缩小数组范围
        // 如果遇到2就交换到最右边，并缩小数组范围
        // 当0和2都摆放在合适的位置之后1自然也就在中间

        // 定义数组范围
        int left = 0;
        int right = nums.length - 1;
        // 记录的要么是1要么不是1，one记录的可能是1，有可能是0
        int one = 0;
        // 遍历一次数组
        while (left <= right) {
            if (nums[left] == 0) {
                // 尝试和1交换位置并缩小范围
                swap(left++, one++);
            } else if (nums[left] == 2) {
                // 直接交换到最后并缩小范围
                // 注意：由于从末尾交换过来的数还是可能是2，所以左边的范围不能改变
                swap(left, right--);
            } else {
                // 此时数组范围缩小了，并且one指向1所处位置
                left++;
            }
        }
    }

    private void swap(int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
